package com.dyz.leetcode._14_binarySearchTree;


import com.dyz.leetcode.Node;
import com.dyz.leetcode.Node1;

import java.util.LinkedList;
import java.util.Queue;

public class _116_connect {
    public Node1 connect(Node1 root) {
        if (root == null) {return null;}
        Queue<Node1> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node1 curr = queue.poll();
                // 如果当前节点不是这一层的最后一个节点，则设置 next
                if (i != size - 1) {curr.next = queue.peek();}
                if (curr.left != null) {queue.offer(curr.left);}
                if (curr.right != null) {queue.offer(curr.right);}
            }
        }
        return root;
    }

    // 2. 双指针
    public Node1 connect3(Node1 root) {
        if (root == null) {return null;}
        Node1 left = root;
        Node1 curr = null;
        while (left.left != null) {
            curr = left;
            while (curr != null) {
                curr.left.next = curr.right;
                if (curr.next != null) {
                    curr.right.next = curr.next.left;
                }
                curr = curr.next;
            }
            left = left.left;
        }
        return root;
    }

    //DFS
    public Node1 connect2(Node1 root){
        if(root==null){return null;}
        dfs2(root);
        return root;
    }

    private void dfs2(Node1 node){
        if(node==null){return;}
        Node1 left = node.left;
        Node1 right = node.right;
        while (left!=null){
            left.next = right;
            left = left.right;
            right = right.left;
        }
        dfs2(node.left);
        dfs2(node.right);
    }
}
